{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Paint N × 3 Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numOfWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给 N x 3 网格图涂色的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一个 <code>n x 3</code>&nbsp;的网格图 <code>grid</code>&nbsp;，你需要用 <strong>红，黄，绿</strong>&nbsp;三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。</p>\n",
    "\n",
    "<p>给你网格图的行数 <code>n</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回给&nbsp;<code>grid</code>&nbsp;涂色的方案数。由于答案可能会非常大，请你返回答案对&nbsp;<code>10^9 + 7</code>&nbsp;取余的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>总共有 12 种可行的方法：\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/04/12/e1.png\" style=\"height: 289px; width: 450px;\">\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>54\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>246\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 7\n",
    "<strong>输出：</strong>106494\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5000\n",
    "<strong>输出：</strong>30228214\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length</code></li>\n",
    "\t<li><code>grid[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-paint-n-3-grid](https://leetcode.cn/problems/number-of-ways-to-paint-n-3-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-paint-n-3-grid](https://leetcode.cn/problems/number-of-ways-to-paint-n-3-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '5000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        M = int(1e9 + 7)\n",
    "        # 三色 f1, 双色 f2\n",
    "        f1 = f2 = 6\n",
    "        for i in range(1, n):\n",
    "            # 每个三色的下一行, 有 2 个三色, 2 个双色\n",
    "            # 每个双色的下一行, 有 2 个三色, 3 个双色\n",
    "            nf1 = f1 * 2 + f2 * 2\n",
    "            nf2 = f1 * 2 + f2 * 3\n",
    "            f1, f2 = nf1 % M, nf2 % M\n",
    "        return (f1 + f2) % M\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        # 121 -> 212 213 232 312 313  a -> 3a 2b\n",
    "        # 123 -> 212 231 232 312      b -> 2a 2b\n",
    "        a = 6\n",
    "        b = 6\n",
    "        ans = 12\n",
    "        for i in range(1, n):\n",
    "            ans = (a * 5 + b * 4) % MOD\n",
    "            a, b = (3 * a + 2 * b) % MOD, (2 * a + 2 * b) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        cons = 10 **9 + 7\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA% cons\n",
    "            ABC = new_ABC% cons\n",
    "        ans = ABA + ABC\n",
    "        return ans % cons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        dp=[1]*12\n",
    "        for _ in range(n-1):\n",
    "            dpx=[0]*12\n",
    "            dpx[0]=(dp[1]+dp[4]+dp[10]+dp[2]+dp[5])%MOD\n",
    "            dpx[3]=(dp[1]+dp[7]+dp[10]+dp[2])%MOD\n",
    "            dpx[6]=(dp[1]+dp[4]+dp[2]+dp[5]+dp[11])%MOD\n",
    "            dpx[9]=(dp[4]+dp[5]+dp[8]+dp[11])%MOD\n",
    "\n",
    "            dpx[1]=(dp[0]+dp[3]+dp[6]+dp[8]+dp[11])%MOD\n",
    "            dpx[4]=(dp[0]+dp[6]+dp[9]+dp[8])%MOD\n",
    "            dpx[7]=(dp[3]+dp[2]+dp[5]+dp[11])%MOD\n",
    "            dpx[10]=(dp[0]+dp[3]+dp[5]+dp[8]+dp[11])%MOD\n",
    "\n",
    "            dpx[2]=(dp[0]+dp[3]+dp[6]+dp[7])%MOD\n",
    "            dpx[5]=(dp[0]+dp[6]+dp[9]+dp[7]+dp[10])%MOD\n",
    "            dpx[8]=(dp[9]+dp[1]+dp[4]+dp[10])%MOD\n",
    "            dpx[11]=(dp[6]+dp[9]+dp[1]+dp[7]+dp[10])%MOD\n",
    "            dp=dpx\n",
    "        return sum(dp)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        fi0, fi1 = 6, 6\n",
    "        for i in range(2, n + 1):\n",
    "            fi0, fi1 = (2 * fi0 + 2 * fi1) % mod, (2 * fi0 + 3 * fi1) % mod\n",
    "        return (fi0 + fi1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        x=6\n",
    "        y=6\n",
    "        t=10**9+7\n",
    "        while n>1:\n",
    "            y=x*2+y*2\n",
    "            x=x+y\n",
    "            n-=1\n",
    "            if x>=t:\n",
    "                x=x%t\n",
    "            if y>=t:\n",
    "                y=y%t\n",
    "\n",
    "        return (x+y)%(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp0=dp1=6\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(1,n):\n",
    "            old_dp0,old_dp1=dp0,dp1\n",
    "            dp0=old_dp0*2+old_dp1*2\n",
    "            dp1=old_dp0*2+old_dp1*3\n",
    "            dp0%=mod\n",
    "            dp1%=mod\n",
    "        return (dp0+dp1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        cons = 10 **9 + 7\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA% cons\n",
    "            ABC = new_ABC% cons\n",
    "        ans = ABA + ABC\n",
    "        return ans % cons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        f0,f1 = 6,6\n",
    "        for i in range(2,n+1):\n",
    "            f0,f1 = (2*f0+2*f1)%MOD,(2*f0+3*f1)%MOD\n",
    "        return (f0+f1)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        cons = 10 **9 + 7\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA% cons\n",
    "            ABC = new_ABC% cons\n",
    "        ans = ABA + ABC\n",
    "        return ans % cons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        x=6\n",
    "        y=6\n",
    "        t=10**9+7\n",
    "        while n>1:\n",
    "            y=x*2+y*2\n",
    "            x=x+y\n",
    "            n-=1\n",
    "            if x>=t:\n",
    "                x=x%t\n",
    "            if y>=t:\n",
    "                y=y%t\n",
    "\n",
    "        return (x+y)%(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        fi0, fi1 = 6, 6\n",
    "        for i in range(2, n + 1):\n",
    "            fi0, fi1 = (2 * fi0 + 2 * fi1) % mod, (2 * fi0 + 3 * fi1) % mod\n",
    "        return (fi0 + fi1) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        data=[]\n",
    "        for x in range(3):\n",
    "            for y in range(3):\n",
    "                for z in range(3):\n",
    "                    if x!=y and y!=z:\n",
    "                        data.append([x,y,z])\n",
    "\n",
    "        maps={}\n",
    "        for i in range(len(data)-1):\n",
    "            for j in range(i+1,len(data)):\n",
    "                if data[i][0]!=data[j][0] and data[i][1]!=data[j][1] and data[i][2]!=data[j][2]:\n",
    "                    if i not in maps:\n",
    "                        maps[i]=[]\n",
    "                    if j not in maps:\n",
    "                        maps[j]=[]\n",
    "                    maps[i].append(j)\n",
    "                    maps[j].append(i)\n",
    "        ans = [1 for _ in range(len(maps))]\n",
    "        lenth = len(ans)\n",
    "        for i in range(n-1):\n",
    "            newans = [0 for _ in range(lenth)]\n",
    "            for idx in range(lenth):\n",
    "                for j in maps[idx]:\n",
    "                    newans[idx] += ans[j]\n",
    "                newans[idx] %= mod\n",
    "            ans = newans\n",
    "        return sum(ans)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "      aba = 6\n",
    "      abc = 6\n",
    "\n",
    "      for _ in range(1, n):\n",
    "        abc = 2 * (aba + abc)\n",
    "        aba += abc\n",
    "        \n",
    "      return (aba + abc) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        t = []\n",
    "        for i in ['0', '1', '2']:\n",
    "            for j in ['0', '1', '2']:\n",
    "                for k in ['0', '1', '2']:\n",
    "                    if i != j and j != k:\n",
    "                        t.append(i + j + k)\n",
    "        dp = [1] * 12\n",
    "        edge = []\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(12):\n",
    "            edge.append([])\n",
    "            for j in range(12):\n",
    "                if self.check(t[i], t[j]):\n",
    "                    edge[i].append(j)\n",
    "        for L in range(n - 1):\n",
    "            dp2 = [0] * 12\n",
    "            for i in range(12):\n",
    "                for j in edge[i]:\n",
    "                    dp2[i] += dp[j]\n",
    "            dp = [x % mod for x in dp2]\n",
    "            \n",
    "        return sum(dp) % mod\n",
    "\n",
    "    def check(self, x, y):\n",
    "        for i in range(len(x)):\n",
    "            if x[i] == y[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp0=dp1=6\n",
    "        mod = 10**9 + 7\n",
    "        for _ in range(1,n):\n",
    "            dp0,dp1=(dp0*2+dp1*2)%mod,(dp0*2+dp1*3)%mod\n",
    "        return (dp0+dp1)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numOfWays(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        NUM = 1e9 + 7\n",
    "        f0, f1= 6, 6\n",
    "        for i in range(2, n+1):\n",
    "            f0, f1 = (2*f0+2*f1) % NUM, (2*f0+3*f1)%NUM\n",
    "        return int((f0 + f1) % NUM)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        aba = 6\n",
    "        abc = 6\n",
    "        mask = 10**9+7\n",
    "        for i in range(1, n):\n",
    "            naba = (3*aba)+(2*abc)\n",
    "            nabc = (2*aba)+(2*abc)\n",
    "            aba, abc = naba%mask, nabc%mask\n",
    "        return (aba+abc)%mask\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        cons = 10 **9 + 7\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = (3*ABA + 2*ABC)% cons\n",
    "            new_ABC = (2*ABA + 2*ABC)% cons\n",
    "            ABA = new_ABA\n",
    "            ABC = new_ABC\n",
    "        ans = ABA + ABC\n",
    "        return ans % cons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = (10**9) + 7\n",
    "        a, b = 1, 1\n",
    "        for i in range(n-1):\n",
    "            b = ((a + b) * 2) % MOD\n",
    "            a = (b + a) % MOD\n",
    "        return (a + b) * 6 % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numOfWays(self, n: int) -> int:\r\n",
    "        mod = 10 ** 9 + 7\r\n",
    "        strs = [\"rbg\",\"rbr\",\"rgb\",\"rgr\",\"brg\",\"bgr\",\"bgb\",\"brb\",\"gbr\",\"grb\",\"gbg\",\"grg\"]\r\n",
    "        mapping = [[] for _ in range(12)]\r\n",
    "        for i in range(12):\r\n",
    "            for j in range(i + 1, 12):\r\n",
    "                if all(x != y for x, y in zip(strs[i], strs[j])):\r\n",
    "                    mapping[i].append(j)\r\n",
    "                    mapping[j].append(i)\r\n",
    "        dp = [[0] * 12 for _ in range(2)]\r\n",
    "        for i in range(12):\r\n",
    "            dp[1][i] = 1\r\n",
    "        for i in range(2, n + 1):\r\n",
    "            for j in range(12):\r\n",
    "                res = 0\r\n",
    "                for x in mapping[j]:\r\n",
    "                    res = (res + dp[(i - 1) % 2][x]) % mod\r\n",
    "                dp[i % 2][j] = res\r\n",
    "        return sum(dp[n % 2]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        t = p = 6\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n - 1):\n",
    "            x, y = t, p\n",
    "            t = (3 * x + 2 * y) % mod\n",
    "            p = (2 * x + 2 * y) % mod\n",
    "        return (t + p) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MODULO = 10 ** 9 + 7\n",
    "        fi0, fi1 = 6, 6\n",
    "        for i in range(2, n + 1):\n",
    "            fi0, fi1 = (2 * fi0 + 2 * fi1) % MODULO, (2 * fi0 + 3 * fi1) %MODULO\n",
    "        return (fi0 + fi1) % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        a = 6\n",
    "        b = 6\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            a, b = (3 * a + 2 * b) % mod, (2 * a + 2 * b) % mod\n",
    "        \n",
    "        return (a + b) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numOfWays(self, n: int) -> int:\r\n",
    "        mod = 10 ** 9 + 7\r\n",
    "        strs = [\"rbg\",\"rbr\",\"rgb\",\"rgr\",\"brg\",\"bgr\",\"bgb\",\"brb\",\"gbr\",\"grb\",\"gbg\",\"grg\"]\r\n",
    "        mapping = [[] for _ in range(12)]\r\n",
    "        for i in range(12):\r\n",
    "            for j in range(12):\r\n",
    "                if all(x != y for x, y in zip(strs[i], strs[j])):\r\n",
    "                    mapping[i].append(j)\r\n",
    "        dp = [[1] * 12 for _ in range(2)]\r\n",
    "        for i in range(2, n + 1):\r\n",
    "            for j in range(12):\r\n",
    "                dp[i % 2][j] = sum(dp[(i + 1) % 2][x] for x in mapping[j]) % mod\r\n",
    "        return sum(dp[n % 2]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        # def isValid(row1:list[int],row2:list[int]) -> bool:\n",
    "        #     for i in range(3):\n",
    "        #         if row1[i]==row2[i]:\n",
    "        #             return False\n",
    "        #     return True\n",
    "        # rows=[[1,2,1],[1,2,3],[1,3,1],[1,3,2],[2,1,2],[2,1,3],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,3]]\n",
    "        # transferMatrix=[[0 for _ in range(len(rows))] for _ in range(len(rows))]\n",
    "        # for _ in range(len(rows)):\n",
    "        #     for __ in range(len(rows)):\n",
    "        #         if isValid(rows[_],rows[__]):\n",
    "        #             transferMatrix[_][__]=1\n",
    "\n",
    "        # counts=[1 for _ in range(len(rows))]\n",
    "        # for layers in range(n-1):\n",
    "        #     newCounts=[0 for _ in range(len(rows))]\n",
    "        #     for Prev in range(len(rows)):\n",
    "        #         for Next in range(len(rows)):\n",
    "        #             newCounts[Next]+=counts[Prev]*transferMatrix[Prev][Next]\n",
    "        #     counts=newCounts.copy()\n",
    "        # answer=0\n",
    "        # for _ in range(len(rows)):\n",
    "        #     answer+=counts[_]\n",
    "        # return mod(answer,10**9+7)\n",
    "\n",
    "        transferMatrix=[[2,2],[2,3]]\n",
    "        counts=[6,6]\n",
    "        for layers in range(n-1):\n",
    "            counts=[counts[0]*2+counts[1]*2,counts[0]*2+counts[1]*3]\n",
    "        return mod(counts[0]+counts[1],10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        abc,aba,ans = 6,6,0\n",
    "        for i in range(n):\n",
    "            ans = abc + aba\n",
    "            abc,aba = abc * 2 + aba * 2 , abc * 2 + aba * 3\n",
    "        mod = 10**9 + 7\n",
    "        ans = ans % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        A, B = 6, 6\n",
    "        M = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            A, B = 3 * A + 2 * B, 2 * A + 2 * B\n",
    "        return (A + B) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        abc,aba,ans = 6,6,0\n",
    "        for i in range(n):\n",
    "            ans = abc + aba\n",
    "            abc,aba = abc * 2 + aba * 2 , abc * 2 + aba * 3\n",
    "        mod = 10**9 + 7\n",
    "        ans = ans % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA\n",
    "            ABC = new_ABC\n",
    "        ans = ABA + ABC\n",
    "        return ans % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        a = 6\n",
    "        b = 6\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            a, b = 3 * a + 2 * b, 2 * a + 2 * b\n",
    "        \n",
    "        return (a + b) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if (n == 0):\n",
    "            return 0\n",
    "        elif (n == 1):\n",
    "            return 12\n",
    "        \n",
    "        ans = 0\n",
    "        ABA = 6\n",
    "        ABC = 6\n",
    "        for i in range(2, n+1):\n",
    "            new_ABA = 3*ABA + 2*ABC\n",
    "            new_ABC = 2*ABA + 2*ABC\n",
    "            ABA = new_ABA\n",
    "            ABC = new_ABC\n",
    "        ans = ABA + ABC\n",
    "        return ans % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        if not n:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 12\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a, b = 6, 6\n",
    "        for i in range(2, n + 1):\n",
    "            x = a * 3 + b * 2\n",
    "            y = a * 2 + b * 2\n",
    "            a, b = x, y \n",
    "\n",
    "        return (a + b) % MOD "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        def isValid(row1:list[int],row2:list[int]) -> bool:\n",
    "            for i in range(3):\n",
    "                if row1[i]==row2[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        rows=[[1,2,1],[1,2,3],[1,3,1],[1,3,2],[2,1,2],[2,1,3],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,3]]\n",
    "        transferMatrix=[[0 for _ in range(len(rows))] for _ in range(len(rows))]\n",
    "        for _ in range(len(rows)):\n",
    "            for __ in range(len(rows)):\n",
    "                if isValid(rows[_],rows[__]):\n",
    "                    transferMatrix[_][__]=1\n",
    "        counts=[1 for _ in range(len(rows))]\n",
    "        for layers in range(n-1):\n",
    "            newCounts=[0 for _ in range(len(rows))]\n",
    "            for Prev in range(len(rows)):\n",
    "                for Next in range(len(rows)):\n",
    "                    newCounts[Next]+=counts[Prev]*transferMatrix[Prev][Next]\n",
    "            counts=newCounts.copy()\n",
    "        answer=0\n",
    "        for _ in range(len(rows)):\n",
    "            answer=mod(answer+counts[_],10**9+7)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        types = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        m = len(types)\n",
    "        valid = [[0 for _ in range(m)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                x1, x2, x3 = types[i] // 9, types[i] // 3 % 3, types[i] % 3 \n",
    "                y1, y2, y3 = types[j] // 9, types[j] // 3 % 3, types[j] % 3 \n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    valid[i][j] = valid[j][i] = 1 \n",
    "        dp = [1] * m\n",
    "        for i in range(2, n + 1):\n",
    "            new = [0] * m \n",
    "            for cur in range(m):\n",
    "                for pre in range(m):\n",
    "                    if valid[pre][cur]:\n",
    "                        new[cur] += dp[pre]\n",
    "                        # new[cur] %= 10 ** 9 + 7\n",
    "            dp = new \n",
    "        return sum(dp) % (10 ** 9 + 7)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        def isValid(row1:list[int],row2:list[int]) -> bool:\n",
    "            for i in range(3):\n",
    "                if row1[i]==row2[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        rows=[[1,2,1],[1,2,3],[1,3,1],[1,3,2],[2,1,2],[2,1,3],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,3]]\n",
    "        transferMatrix=[[0 for _ in range(len(rows))] for _ in range(len(rows))]\n",
    "        for _ in range(len(rows)):\n",
    "            for __ in range(len(rows)):\n",
    "                if isValid(rows[_],rows[__]):\n",
    "                    transferMatrix[_][__]=1\n",
    "        counts=[1 for _ in range(len(rows))]\n",
    "        for layers in range(n-1):\n",
    "            newCounts=[0 for _ in range(len(rows))]\n",
    "            for Prev in range(len(rows)):\n",
    "                for Next in range(len(rows)):\n",
    "                    newCounts[Next]+=counts[Prev]*transferMatrix[Prev][Next]\n",
    "            counts=newCounts.copy()\n",
    "        answer=0\n",
    "        for _ in range(len(rows)):\n",
    "            answer+=counts[_]\n",
    "        return mod(answer,10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp=[[0]*2 for _ in range(n)]\n",
    "        dp[0][0]=dp[0][1]=6\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]+=dp[i-1][0]*2\n",
    "            dp[i][0]+=dp[i-1][1]*2\n",
    "            dp[i][1]+=dp[i-1][0]*2\n",
    "            dp[i][1]+=dp[i-1][1]*3\n",
    "            dp[i][0]%=mod\n",
    "            dp[i][1]%=mod\n",
    "        return sum(dp[n-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        def isValid(row1:list[int],row2:list[int]) -> bool:\n",
    "            for i in range(3):\n",
    "                if row1[i]==row2[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        rows=[[1,2,1],[1,2,3],[1,3,1],[1,3,2],[2,1,2],[2,1,3],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,3]]\n",
    "        transferMatrix=[[0 for _ in range(len(rows))] for _ in range(len(rows))]\n",
    "        for _ in range(len(rows)):\n",
    "            for __ in range(len(rows)):\n",
    "                if isValid(rows[_],rows[__]):\n",
    "                    transferMatrix[_][__]=1\n",
    "        counts=[1 for _ in range(len(rows))]\n",
    "        for layers in range(n-1):\n",
    "            newCounts=[0 for _ in range(len(rows))]\n",
    "            for Prev in range(len(rows)):\n",
    "                for Next in range(len(rows)):\n",
    "                    newCounts[Next]+=counts[Prev]*transferMatrix[Prev][Next]\n",
    "            counts=newCounts.copy()\n",
    "        answer=0\n",
    "        for _ in range(len(rows)):\n",
    "            answer+=counts[_]\n",
    "        return mod(answer,10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        s=n\n",
    "        dp=[[0]*2 for _ in range(n)]\n",
    "        \n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        mod=10**9+7\n",
    "        for i in range(1,n):\n",
    "          dp[i][0]=(dp[i-1][0]*3+dp[i-1][1]*2)%mod\n",
    "          dp[i][1]=(dp[i-1][0]*2+dp[i-1][1]*2)%mod\n",
    "       #print(dp)\n",
    "        return sum(dp[-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        f = [[0] * 2 for _ in range(n + 1)]\n",
    "\n",
    "        # abc\n",
    "        f[1][0] = 6\n",
    "        # aba\n",
    "        f[1][1] = 6\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            f[i][0] = (f[i-1][0] * 3 + f[i-1][1] * 2) % mod\n",
    "            f[i][1] = (f[i-1][0] * 2 + f[i-1][1] * 2 ) % mod\n",
    "        \n",
    "        return sum(f[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 预处理出所有满足条件的 type\n",
    "        types = list()\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        # 只要相邻的颜色不相同就行\n",
    "                        # 将其以十进制的形式存储\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        type_cnt = len(types)\n",
    "        # 预处理出所有可以作为相邻行的 type 对\n",
    "        related = [[0] * type_cnt for _ in range(type_cnt)]\n",
    "        for i, ti in enumerate(types):\n",
    "            # 得到 types[i] 三个位置的颜色\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                # 得到 types[j] 三个位置的颜色\n",
    "                y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3\n",
    "                # 对应位置不同色，才能作为相邻的行\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    related[i][j] = 1\n",
    "        # 递推数组\n",
    "        f = [[0] * type_cnt for _ in range(n + 1)]\n",
    "        # 边界情况，第一行可以使用任何 type\n",
    "        f[1] = [1] * type_cnt\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(type_cnt):\n",
    "                for k in range(type_cnt):\n",
    "                    # f[i][j] 等于所有 f[i - 1][k] 的和\n",
    "                    # 其中 k 和 j 可以作为相邻的行\n",
    "                    if related[k][j]:\n",
    "                        f[i][j] += f[i - 1][k]\n",
    "                        f[i][j] %= mod\n",
    "        # 最终所有的 f[n][...] 之和即为答案\n",
    "        ans = sum(f[n]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        kind = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        kind.append(f'{i}{j}{k}')\n",
    "        # print(kind)\n",
    "        m = len(kind)\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        for i in range(m):\n",
    "            f[0][i] = 1\n",
    "        # d = [[0] * m for _ in range(m)]\n",
    "        # for i in range(m):\n",
    "        #     for j in range(m):\n",
    "        #         if all(kind[i][k] != kind[j][k] for k in range(3)]:\n",
    "        #             d[i][j] = 1 \n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if all(kind[j][p] != kind[k][p] for p in range(3)):\n",
    "                        f[i][j] = (f[i][j] + f[i - 1][k]) % MOD\n",
    "        return sum(f[n - 1]) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        types = []\n",
    "        for i in range (3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        \n",
    "        m = len(types)\n",
    "        match = [[0] * m for _ in range(m)]\n",
    "        for i, ti in enumerate(types):\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                y1, y2, y3 = tj // 9, tj //3 % 3, tj % 3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    match[i][j] = 1\n",
    "        \n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[1] = [1] * 12\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if match[j][k]:\n",
    "                        f[i][j] = (f[i][j] + f[i-1][k]) % mod\n",
    "        \n",
    "        return sum(f[-1]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        # 与处理出type\n",
    "        types = list()\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        type_cnt = len(types)\n",
    "        match = [[0] * type_cnt for _ in range(type_cnt)]\n",
    "\n",
    "        for i, ti in enumerate(types):\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    match[i][j] = 1\n",
    "        \n",
    "        # 递推\n",
    "        f = [[0] * type_cnt for _ in range(n + 1)]\n",
    "        f[1] = [1] * type_cnt\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(type_cnt):\n",
    "                for k in range(type_cnt):\n",
    "                    # j接在k的后面\n",
    "                    if match[k][j]:\n",
    "                        f[i][j] =  (f[i][j] + f[i-1][k]) % mod\n",
    "        return sum(f[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 预处理出所有满足条件的 type\n",
    "        types = list()\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        # 只要相邻的颜色不相同就行\n",
    "                        # 将其以十进制的形式存储\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        type_cnt = len(types)\n",
    "        # 预处理出所有可以作为相邻行的 type 对\n",
    "        related = [[0] * type_cnt for _ in range(type_cnt)]\n",
    "        for i, ti in enumerate(types):\n",
    "            # 得到 types[i] 三个位置的颜色\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                # 得到 types[j] 三个位置的颜色\n",
    "                y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3\n",
    "                # 对应位置不同色，才能作为相邻的行\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    related[i][j] = 1\n",
    "        # 递推数组\n",
    "        f = [[0] * type_cnt for _ in range(n + 1)]\n",
    "        # 边界情况，第一行可以使用任何 type\n",
    "        f[1] = [1] * type_cnt\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(type_cnt):\n",
    "                for k in range(type_cnt):\n",
    "                    # f[i][j] 等于所有 f[i - 1][k] 的和\n",
    "                    # 其中 k 和 j 可以作为相邻的行\n",
    "                    if related[k][j]:\n",
    "                        f[i][j] += f[i - 1][k]\n",
    "                        f[i][j] %= mod\n",
    "        # 最终所有的 f[n][...] 之和即为答案\n",
    "        ans = sum(f[n]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        types = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        typesCnt = len(types)\n",
    "        # 预处理出所有可以作为相邻行的 type 对\n",
    "        canType = [[0] * typesCnt for _ in range(typesCnt)]\n",
    "        for i in range(typesCnt):\n",
    "            for j in range(typesCnt):\n",
    "                if i != j:\n",
    "                    a = [types[i] // 9, (types[i] % 9) // 3, types[i] % 3]\n",
    "                    b = [types[j] // 9, (types[j] % 9) // 3, types[j] % 3]\n",
    "                    if a[0] != b[0] and a[1] != b[1] and a[2] != b[2]:\n",
    "                        canType[i][j] = 1\n",
    "\n",
    "        dp = [[0] * typesCnt for _ in range(n)]\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(typesCnt):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(typesCnt):\n",
    "                for k in range(typesCnt):\n",
    "                    if canType[j][k] == 1:\n",
    "                        dp[i][j] += dp[i - 1][k]\n",
    "                        dp[i][j] %= mod\n",
    "        return sum(x % mod for x in dp[n - 1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        types = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        \n",
    "        m = len(types)\n",
    "        match = [[0] * m for _ in range(m)]\n",
    "\n",
    "        for i, ti in enumerate(types):\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    match[i][j] = 1\n",
    "        \n",
    "        # 递推\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[1] = [1] * m\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if match[k][j]:\n",
    "                        f[i][j] = (f[i][j] + f[i-1][k]) % mod\n",
    "        \n",
    "        return sum(f[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        types = []\n",
    "        for i in range (3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        \n",
    "        m = len(types)\n",
    "        match = [[0] * m for _ in range(m)]\n",
    "        for i, ti in enumerate(types):\n",
    "            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3\n",
    "            for j, tj in enumerate(types):\n",
    "                y1, y2, y3 = tj // 9, tj //3 % 3, tj % 3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    match[i][j] = 1\n",
    "        \n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[1] = [1] * m\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if match[j][k]:\n",
    "                        f[i][j] = (f[i][j] + f[i-1][k]) % mod\n",
    "        \n",
    "        return sum(f[-1]) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        # 红：2,黄：1,绿,0 用一个三进制数表示一行的颜色方案\n",
    "        # 然后会得到一个所有无重复的一行颜色方案共12种，放入一个集合\n",
    "        # 枚举这12种方案，对于其中一种方案mask，其d[mask]:mask'表示与mask不重复的颜色方案\n",
    "        # dp[i][mask] = sum(dp[i-1][mask'] for mask' in d[mask])\n",
    "        # return sum(dp[0][mask] for mask in 12种方案)\n",
    "        # 预处理12种方案\n",
    "        masks = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        masks.append(i*9+j*3+k)\n",
    "        \n",
    "        m = len(masks)\n",
    "        # d[i][j]表示i,j两行可以作为相邻的两行，也就是无重复的两行\n",
    "        d = [[0]*m for _ in range(m)]\n",
    "        # 预处理d\n",
    "        for i,vi in enumerate(masks):\n",
    "            # 取每一位和十进制一样，110,110//100,110//10%10,110%10\n",
    "            x1,x2,x3 = vi//9,vi//3%3,vi%3\n",
    "            for j,vj in enumerate(masks):\n",
    "                y1,y2,y3 = vj//9,vj//3%3,vj%3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    d[i][j] = 1\n",
    "        # 动态规划\n",
    "        f = [[0]*m for _ in range(n)]\n",
    "        f[0] = [1]*m\n",
    "        for i in range(1,n):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if d[j][k]:\n",
    "                        f[i][j] += f[i-1][k]\n",
    "                        f[i][j] %= mod\n",
    "        return sum(f[n-1])%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        masks = []\n",
    "        # 统计12种方案\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        masks.append(i*9+j*3+k)\n",
    "        # dp[i][k]表示第i行涂色方案为k有多少种涂色方案\n",
    "        # dp[i-1][k']，k'表示与k涂色方案不重合的方案\n",
    "        m = len(masks)\n",
    "        d = [[0]*m for _ in range(m)]\n",
    "        for i,s1 in enumerate(masks):\n",
    "            for j,s2 in enumerate(masks):\n",
    "                x1,x2,x3 = s1//9,s1//3%3,s1%3\n",
    "                y1,y2,y3 = s2//9,s2//3%3,s2%3\n",
    "                if x1 != y1 and x2 != y2 and x3 != y3:\n",
    "                    d[i][j] = 1\n",
    "        # 动态规划\n",
    "        dp = [[0]*m for _ in range(n)]\n",
    "        dp[0] = [1]*m\n",
    "        for i in range(1,n):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if d[j][k]:\n",
    "                        dp[i][j] += dp[i-1][k]\n",
    "                        dp[i][j] %= mod\n",
    "        return sum(dp[n-1])%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [[0] * 12 for _ in range(5000)]\n",
    "dp[0] = [1] * 12\n",
    "# 0 = 4 + 5 + 7 + 8 + 9\n",
    "# 1 = 4 + 6 + 7 + 8\n",
    "# 2 = 4 + 5 + 8 + 9 + 11\n",
    "# 3 = 5 + 9 + 10 + 11\n",
    "# 4 = 0 + 1 + 2 +10 + 11\n",
    "# 5 = 0 + 2 + 3 + 10\n",
    "# 6 = 1 + 8 + 9 + 11\n",
    "# 7 = 0 + 1 + 9 + 10 + 11\n",
    "# 8 = 0 + 1 + 2 + 6\n",
    "# 9 = 0 + 2 + 3 +6 + 7\n",
    "# 10 = 3 + 4 + 5 + 7\n",
    "# 11 = 2 + 3 + 4 + 6 + 7\n",
    "for i in range(1, 5000):\n",
    "    dp[i][0] = (dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][7] + dp[i - 1][8] + dp[i - 1][9]) % (10 ** 9 + 7)\n",
    "    dp[i][1] = (dp[i - 1][4] + dp[i - 1][6] + dp[i - 1][7] + dp[i - 1][8]) % (10 ** 9 + 7)\n",
    "    dp[i][2] = (dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][8] + dp[i - 1][9] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][3] = (dp[i - 1][5] + dp[i - 1][9] + dp[i - 1][10] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][4] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][10] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][5] = (dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][10]) % (10 ** 9 + 7)\n",
    "    dp[i][6] = (dp[i - 1][1] + dp[i - 1][8] + dp[i - 1][9] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][7] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][9] + dp[i - 1][10] + dp[i - 1][11]) % (10 ** 9 + 7)\n",
    "    dp[i][8] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][6]) % (10 ** 9 + 7)\n",
    "    dp[i][9] = (dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][6] + dp[i - 1][7]) % (10 ** 9 + 7)\n",
    "    dp[i][10] = (dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][7]) % (10 ** 9 + 7)\n",
    "    dp[i][11] = (dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][6] + dp[i - 1][7]) % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        return sum(dp[n - 1]) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def numOfWays(self, n: int) -> int:\n",
    "        types = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i != j and j != k:\n",
    "                        types.append(i * 9 + j * 3 + k)\n",
    "        typesCnt = len(types)\n",
    "        # 预处理出所有可以作为相邻行的 type 对\n",
    "        canType = [[0] * typesCnt for _ in range(typesCnt)]\n",
    "        for i in range(typesCnt):\n",
    "            for j in range(typesCnt):\n",
    "                if i != j:\n",
    "                    a = [types[i] // 9, (types[i] % 9) // 3, types[i] % 3]\n",
    "                    b = [types[j] // 9, (types[j] % 9) // 3, types[j] % 3]\n",
    "                    if a[0] != b[0] and a[1] != b[1] and a[2] != b[2]:\n",
    "                        canType[i][j] = 1\n",
    "\n",
    "        dp = [[0] * typesCnt for _ in range(n)]\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(typesCnt):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(typesCnt):\n",
    "                for k in range(typesCnt):\n",
    "                    if canType[j][k] == 1:\n",
    "                        dp[i][j] += dp[i - 1][k]\n",
    "                        dp[i][j] %= mod\n",
    "        return sum(x % mod for x in dp[n - 1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        # 红：1 黄:2 绿3：\n",
    "        data=[[1, 2, 1], [1, 2, 3], [1, 3, 1], [1, 3, 2],\n",
    "              [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2],\n",
    "              [3, 2, 1], [3, 2, 3], [3, 1, 2], [3, 1, 3]]\n",
    "\n",
    "        nm=12\n",
    "        g=[[1 for i in range(12)] for i in range(12)]\n",
    "        for i in range(nm):\n",
    "            for j in range(nm):\n",
    "                can=True\n",
    "                for k in range(3):\n",
    "                    if data[i][k]==data[j][k]:\n",
    "                        can=False\n",
    "                        break\n",
    "                if can:\n",
    "                    g[i][j],g[j][i]=True,True\n",
    "                else:\n",
    "                    g[i][j],g[j][i]=False,False\n",
    "\n",
    "        dp=[[0 for i in range(nm)] for i in range(n)]\n",
    "        for i in range(12):\n",
    "            dp[0][i]=1\n",
    "\n",
    "        if n==1:return sum(dp[0])\n",
    "        for p in range(1,n):\n",
    "            for i in range(nm):\n",
    "                for j in range(nm):\n",
    "                    if g[i][j]==True:\n",
    "                        dp[p][j]=(dp[p][j]+dp[p-1][i])%(10**9+7)\n",
    "\n",
    "        return sum(dp[n-1])%(10**9+7)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    n=3\n",
    "    test = Solution()\n",
    "    l3 = test.numOfWays(n)\n",
    "    print('l3= %s'%l3)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        # 0,1,2,red,yellow,green\n",
    "        mod = int(1e9 + 7)\n",
    "        # 一行内不冲突\n",
    "        typeList = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if i == j or j == k:\n",
    "                        continue\n",
    "                    val = i * 9 + j * 3 + k * 1\n",
    "                    typeList.append(val)\n",
    "        def toBit(i, j, k):\n",
    "            return i * 9 + j * 3 + k * 1\n",
    "\n",
    "\n",
    "        def bitCov(val):\n",
    "            res = [0] * 3\n",
    "            for i in range(3):\n",
    "                div, mod = divmod(val, 3)\n",
    "                res[3 - 1 - i] = mod\n",
    "                val = div\n",
    "            \n",
    "            return res\n",
    "\n",
    "        #行间不冲突\n",
    "        checkMat = [[False] * len(typeList) for _ in range(len(typeList))]\n",
    "        for i in range(len(typeList)):\n",
    "            for j in range(len(typeList)):\n",
    "                \n",
    "                ii = bitCov(typeList[i])\n",
    "                jj = bitCov(typeList[j])\n",
    "\n",
    "                if ii[0] == jj[0] or ii[1] == jj[1] or ii[2] == jj[2]:\n",
    "                    checkMat[i][j] = True\n",
    "        \n",
    "\n",
    "\n",
    "        dp = [[1] * len(typeList) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(2, len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                dp[i][j] = 0\n",
    "                for k in range(len(typeList)):\n",
    "                    dp[i][j] += dp[i - 1][k] if not checkMat[j][k] else 0\n",
    "                    dp[i][j] %= mod\n",
    "        \n",
    "        return sum(dp[-1]) % mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        f = [[0] * 2 for _ in range(n + 1)]\n",
    "        # ABC, ABA\n",
    "        f[1][0] = 6\n",
    "        f[1][1] = 6\n",
    "        for i in range(2, n+1):\n",
    "            f[i][0] = f[i-1][0] * 3 + f[i-1][1] * 2\n",
    "            f[i][1] = f[i-1][0] * 2 + f[i-1][1] * 2\n",
    "        \n",
    "        return sum(f[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mode=10**9+7\n",
    "        # @cache\n",
    "        # def dfs(k,c):\n",
    "        #     if k==n:\n",
    "        #         return 1\n",
    "        #     elif k==0:\n",
    "        #         return 6*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "        #     else:\n",
    "        #         if c==0:\n",
    "        #             return 2*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "        #         else:\n",
    "        #             return (2*dfs(k+1,0)+3*dfs(k+1,1))%mode\n",
    "        # return dfs(0,0)\n",
    "        dp=[[0]*2 for i in range(n)]\n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=3*dp[i-1][0]+dp[i-1][1]*2\n",
    "            dp[i][1]=2*dp[i-1][0]+2*dp[i-1][1]\n",
    "        return (dp[n-1][0]+dp[n-1][1])%mode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp=[[0 for i in range(2)] for j in range(n)]\n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        if n>=2:\n",
    "            for k in range(1,n):\n",
    "                dp[k][0]=dp[k-1][0]*3+dp[k-1][1]*2\n",
    "                dp[k][1]=dp[k-1][0]*2+dp[k-1][1]*2\n",
    "        return (dp[n-1][0]+dp[n-1][1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        '''\n",
    "        上一行是双色ABA:下一行情况：双色：BAB,BCB,CAC, 三色：BAC,CAB\n",
    "        上一行是三色ABC:下一行情况: 双色：BAB,BCB      三色：BCA,BAC\n",
    "        dp[i][0]表示当前行双色情况的种类数目\n",
    "        dp[i][1]表示当前行三色情况的种类数目\n",
    "        dp[i][0] = dp[i-1][0]*3 + dp[i-1][1]*2\n",
    "        dp[i][1] = dp[i-1][0]*2 + dp[i-1][1]*2\n",
    "        '''\n",
    "        dp = [[0 for i in range(2)] for j in range(n)]\n",
    "        dp[0][0], dp[0][1] = 6, 6\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = dp[i-1][0]*3 + dp[i-1][1]*2\n",
    "            dp[i][1] = dp[i-1][0]*2 + dp[i-1][1]*2\n",
    "        return (dp[-1][0]+dp[-1][1])%(int(1e9+7))\n",
    "\n",
    "# 作者：soiam2014\n",
    "# 链接：https://leetcode.cn/problems/number-of-ways-to-paint-n-3-grid/solutions/199022/5383gei-nx3wang-ge-tu-tu-se-de-fang-an-shu-by-soia/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp=[[0 for i in range(2)] for j in range(n)]\n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        if n>=2:\n",
    "            for k in range(1,n):\n",
    "                dp[k][0]=dp[k-1][0]*3+dp[k-1][1]*2\n",
    "                dp[k][1]=dp[k-1][0]*2+dp[k-1][1]*2\n",
    "        return (dp[n-1][0]+dp[n-1][1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        dp=[[0 for i in range(2)] for j in range(n)]\n",
    "        dp[0][0]=6\n",
    "        dp[0][1]=6\n",
    "        if n>=2:\n",
    "            for k in range(1,n):\n",
    "                dp[k][0]=dp[k-1][0]*3+dp[k-1][1]*2\n",
    "                dp[k][1]=dp[k-1][0]*2+dp[k-1][1]*2\n",
    "        return (dp[n-1][0]+dp[n-1][1])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#  下层的结果 = ABA类的个数 + ABC类的个数 = (3m+2n) + (2m+2n)\n",
    "MOD = 10 ** 9 + 7\n",
    "rec = {1: (6, 6)}\n",
    "for i in range(2, 50001):\n",
    "    m, n = rec[i - 1]\n",
    "    rec[i] = ((3 * m + 2 * n) % MOD, (2 * m + 2 * n) % MOD)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        return sum(rec[n]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c):#i为当前的行下标，c为上一层是哪种排列\n",
    "            if i == n:#当已经铺满\n",
    "                return 1\n",
    "            elif i == 0:#特殊情况，第一层\n",
    "                return 6 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "            else:\n",
    "                if c == 0:#如果上层为ABC\n",
    "                    return 2 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "                else:#如果上层为ABA\n",
    "                    return (2 * dfs(i + 1, 0) + 3 * dfs(i + 1, 1)) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mode=10**9+7\n",
    "        @cache\n",
    "        def dfs(k,c):\n",
    "            if k==n:\n",
    "                return 1\n",
    "            elif k==0:\n",
    "                return 6*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "            else:\n",
    "                if c==0:\n",
    "                    return 2*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "                else:\n",
    "                    return (2*dfs(k+1,0)+3*dfs(k+1,1))%mode\n",
    "        return dfs(0,0)\n",
    "        # dp=[[0]*2 for i in range(n)]\n",
    "        # dp[0][0]=6\n",
    "        # dp[0][1]=6\n",
    "        # for i in range(1,n):\n",
    "        #     dp[i][0]=3*dp[i-1][0]+dp[i-1][1]*2\n",
    "        #     dp[i][1]=2*dp[i-1][0]+2*dp[i-1][1]\n",
    "        # return (dp[n-1][0]+dp[n-1][1])%mode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c):#i为当前的行下标，c为上一层是哪种排列\n",
    "            if i == n:#当已经铺满\n",
    "                return 1\n",
    "            elif i == 0:#特殊情况，第一层\n",
    "                return 6 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "            else:\n",
    "                if c == 0:#如果上层为ABC\n",
    "                    return 2 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "                else:#如果上层为ABA\n",
    "                    return (2 * dfs(i + 1, 0) + 3 * dfs(i + 1, 1)) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c):#i为当前的行下标，c为上一层是哪种排列\n",
    "            if i == n:#当已经铺满\n",
    "                return 1\n",
    "            elif i == 0:#特殊情况，第一层\n",
    "                return 6 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "            else:\n",
    "                if c == 0:#如果上层为ABC\n",
    "                    return 2 * (dfs(i + 1, 0) + dfs(i + 1, 1)) % mod\n",
    "                else:#如果上层为ABA\n",
    "                    return (2 * dfs(i + 1, 0) + 3 * dfs(i + 1, 1)) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, 0)\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mode=10**9+7\n",
    "        @cache\n",
    "        def dfs(k,c):\n",
    "            if k==n:\n",
    "                return 1\n",
    "            elif k==0:\n",
    "                return 6*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "            else:\n",
    "                if c==0:\n",
    "                    return 2*(dfs(k+1,0)+dfs(k+1,1))%mode\n",
    "                else:\n",
    "                    return (2*dfs(k+1,0)+3*dfs(k+1,1))%mode\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        md=10**9+7\n",
    "        arr=[1]*12\n",
    "        while n>1:\n",
    "            newarr=[0]*12\n",
    "            newarr[0]=arr[4]+arr[5]+arr[7]+arr[8]+arr[9]\n",
    "            newarr[1]=arr[4]+arr[6]+arr[7]+arr[8]\n",
    "            newarr[2]=arr[4]+arr[5]+arr[8]+arr[9]+arr[11]\n",
    "            newarr[3]=arr[5]+arr[9]+arr[10]+arr[11]\n",
    "            newarr[4]=arr[0]+arr[1]+arr[2]+arr[10]+arr[11]\n",
    "            newarr[5]=arr[0]+arr[2]+arr[3]+arr[10]\n",
    "            newarr[6]=arr[1]+arr[8]+arr[9]+arr[11]\n",
    "            newarr[7]=arr[0]+arr[1]+arr[9]+arr[10]+arr[11]\n",
    "            newarr[8]=arr[0]+arr[1]+arr[2]+arr[6]\n",
    "            newarr[9]=arr[0]+arr[2]+arr[3]+arr[6]+arr[7]\n",
    "            newarr[10]=arr[3]+arr[4]+arr[5]+arr[7]\n",
    "            newarr[11]=arr[2]+arr[3]+arr[4]+arr[6]+arr[7]\n",
    "            arr=np.array(newarr)%md\n",
    "            n-=1\n",
    "        return int(sum(arr)%md)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos,pre):\n",
    "            if pos==n:return 1\n",
    "            ans=0\n",
    "            \n",
    "            for i in range(3):\n",
    "\n",
    "                for j in range(3):\n",
    "\n",
    "                    for k in range(3):\n",
    "\n",
    "                        temp=(i,j,k)\n",
    "\n",
    "                        if i==j or j==k or i==pre[0] or j==pre[1] or k==pre[2]:\n",
    "                            continue\n",
    "                        ans+=dfs(pos+1,temp)\n",
    "\n",
    "\n",
    "            return ans%mod\n",
    "\n",
    "        return dfs(0,(-1,-1,-1))%mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos,pre):\n",
    "            if pos==n:return 1\n",
    "            ans=0\n",
    "            \n",
    "            for i in range(3):\n",
    "                if i==pre[0]:continue\n",
    "\n",
    "                for j in range(3):\n",
    "                    if j==pre[1]:continue\n",
    "                    if j==i:continue\n",
    "\n",
    "                    for k in range(3):\n",
    "                        if k==pre[2]:continue\n",
    "                        if k==j:continue\n",
    "\n",
    "                        temp=(i,j,k)\n",
    "                        ans+=dfs(pos+1,temp)\n",
    "\n",
    "\n",
    "            return ans%mod\n",
    "\n",
    "        return dfs(0,(-1,-1,-1))%mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        colors = [(0, 1, 0), (1, 0, 1), (2, 0, 1), (0, 1, 2), (1, 0, 2), (2, 0, 2), (0, 2, 0), (1, 2, 0), (2, 1, 0), (0, 2, 1), (1, 2, 1), (2, 1, 2)]\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i, a, b, c) :\n",
    "            if i == n :\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for t1, t2, t3 in colors :\n",
    "                if t1 != a and t2 != b and t3 != c and t1 != t2 and t2 != t3:\n",
    "                    res += (dfs(i+1, t1, t2, t3)) % mod\n",
    "            \n",
    "            return res % mod\n",
    "        \n",
    "        return dfs(0, -1, -1, -1)  % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = 10**9 +7\n",
    "        res = 0\n",
    "        method = [121, 123, 131, 132, 212, 213, 231, 232, 312, 313, 321, 323]\n",
    "        g = [[] for _ in range(12)]\n",
    "        for a in range(12):\n",
    "            for b in range(a):\n",
    "                i, j = method[a], method[b]\n",
    "                if i % 10 != j % 10 and i % 100 // 10 != j % 100 // 10 and i // 100 != j // 100:\n",
    "                    g[a].append(b)\n",
    "                    g[b].append(a)\n",
    "        fun = [[0]*12 for _ in range(n)] + [[1]*12]\n",
    "        for now in range(n-1, 0, -1):\n",
    "            for i in range(11, -1, -1):\n",
    "                for nex in g[i]:\n",
    "                    fun[now][i] += fun[now+1][nex]\n",
    "        return sum(fun[1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfWays(self, n: int) -> int:\n",
    "        MOD = 10**9 +7\n",
    "        g = [[4,5,7,8,9],[4,6,7,8],[4,5,8,9,11],[5,9,10,11],[0,1,2,10,11],[0,2,3,10],[1,8,9,11],[0,1,9,10,11],[0,1,2,6],[0,2,3,6,7],[3,4,5,7],[2,3,4,6,7]]\n",
    "        fun = [[0]*12 for _ in range(n)] + [[1]*12]\n",
    "        for now in range(n-1, 0, -1):\n",
    "            for i in range(11, -1, -1):\n",
    "                for nex in g[i]:\n",
    "                    fun[now][i] += fun[now+1][nex]\n",
    "        return sum(fun[1]) % MOD"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
